package JackSu.aobing;

import java.util.ArrayList;
import java.util.List;

/**
 * PartitionPalindrome
 *
 * @author Syzer
 * @Description 分割回文串
 * @Date 2021/7/16 19:01
 */
public class PartitionPalindrome {
    private int[][] f;
    private List<List<String>> result = new ArrayList<>();

    public List<List<String>> partition(String s) {
        int len = s.length();
        f = new int[len][len];
        recursion(s, new ArrayList<String>(), 0, s.length());
        return result;
    }

    public void recursion(String s, List<String> list, int n, int len) {
        if(n == len) {
            result.add(new ArrayList<String>(list));
            return;
        }
        for(int i = n;i < len;i++) {
            if(isValidate(s, n, i) == 1) {
                list.add(s.substring(n, i + 1));
                recursion(s, list, i + 1, len);
                list.remove(list.size() - 1);
            }
        }
    }

    private int isValidate(String s, int i, int j) {
        if(f[i][j] != 0) {
            return f[i][j];
        }
        if(i >= j) {
            f[i][j] = 1;
        } else if (s.charAt(i) == s.charAt(j)) {
            f[i][j] = isValidate(s, i + 1, j - 1);
        } else {
            f[i][j] = 0;
        }
        return f[i][j];
    }

    public static void main(String[] args) {
        System.out.println(new PartitionPalindrome().partition("aababc"));
    }
}
